Recent developments in Global Position System (GPS) and terrestrial mobile communications make it desirable to integrate GPS functionality into mobile communications devices such as cellular mobile stations. The cellular geolocation problem can be solved using either network-based methods or using handset-based methods.
Terrestrial Location
Network-based solutions rely on the signal transmitted from the mobile station and received at multiple fixed base stations. This can be accomplished by measuring the Time of Arrival (TOA) of the mobile station signal at the base stations. The mobile will lie on a hyperbola defined by the difference in time of arrival of the same signal at different base stations. An accurate position estimate depends on accurate synchronization and signal structure (bandwidth, etc.).
GPS-based Location
GPS-based location relies on a constellation of 24 satellites (plus one or more in-orbit spares) circling the earth every 12 hours. The satellites are at an altitude of 26,000 km. Each satellite transmits two signals: L1 (1575.42 MHz) and L2 (1227.60 MHz). The L1 signal is modulated with two Pseudo-random Noise (PN) codes-the protected (P) code and the coarse/acquisition (C/A) code. The L2 signal carries only the P code. Each satellite transmits a unique code, allowing the receiver to identify the signals. Civilian navigation receivers use only the C/A on the L1 frequency.
The idea behind GPS is to use satellites in space as reference points to determine location. By accurately measuring the distance from three satellites, the receiver "triangulates" its position anywhere on earth. The receiver measures distance by measuring the time required for the signal to travel from the satellite to the receiver. However, the problem in measuring the travel time is to know exactly when the signal left the satellite. To accomplish this, all the satellites and the receivers are synchronized in such a way that they generate the same code at exactly the same time. Hence, by knowing the time that the signal left the satellite, and observing the time it receives the signal based on its internal clock, the receiver can determine the travel time of the signal. If the receiver has an accurate clock synchronized with the GPS satellites, three measurements from three satellites are sufficient to determine position in three dimensions. Each pseudorange (PR) measurement gives a position on the surface of a sphere centered at the corresponding satellite. The GPS satellites are placed in a very precise orbit according to the GPS master plan. GPS receivers have a stored "almanac" which indicates where each satellite is in the sky at a given time. Ground stations continuously monitor GPS satellites to observe their variation in orbit. Once the satellite position has been measured, the information is relayed back to the satellite and the satellite broadcasts these minor errors "ephemeris" along with its timing information as part of the navigation message.
It is very expensive to have an accurate clock at the GPS receiver. In practice, GPS receivers measure time of arrival differences from four satellites with respect to its own dock and then solve for both the user's position and the clock bias with respect to GPS time. FIG. 1 shows four satellites 101, 102, 103, 104 and a GPS receiver 105. Measuring time of arrival differences from four satellites involves solving a system of four equations with four unknowns given the PR measurements and satellite positions (satellite data) as shown in FIG. 1. In other words, due to receiver clock error, the four spheres will not intersect at a single point. The receiver then adjusts its clock such that the four spheres intersect at one point.
Hybrid Position Location System
The terrestrial location solution and the GPS solution complement each other. For example, in rural and suburban areas not too many base stations can hear the mobile station, but a GPS receiver can see four or more satellites. Conversely, in dense urban areas and inside buildings, GPS receivers may not detect enough satellites. However, the mobile station can see two or more base stations. The hybrid solution takes advantage of cellular/PCS information that is already available to both the mobile station and the network. Combining GPS and terrestrial measurements provides substantial improvements in the availability of the location solution. The hybrid position location system may combine Round-trip Delay (RTD) and Pilot phase measurements from the terrestrial network with GPS measurements.
The hybrid approach merges GPS and network measurements to compute the location of the mobile station. The mobile station collects measurements from the GPS constellation and cellular/PCS network. These measurements are fused together to produce an estimate of the mobile station position.
When enough GPS measurements are available, it is unnecessary to use network measurements. However, when there are less than four satellites or, in the case of bad geometry, four or more satellite measurements, the measurements must be complemented with network measurements. The minimum number of measurements for obtaining a solution will be equal to the number of unknowns. Since the system has four unknowns (three coordinates and GPS receiver time bias) the minimum number of measurements to obtain a solution will be four. For any satellite measurements that are not available, round trip delay (RTD) measurements may be used to determine the range to a base station. RTD measurements may also be used to provide time aiding information. In addition other information, such as PN offset pseudo-ranges (if time bias is the same as for satellites), PN offset differences (if time bias is different) and altitude aiding may be used to provide additional information and thus increase the number of equations that include the unknowns being sought (i.e., x, y, z, and time offset). As long as the total number of equations is larger than four it will be possible to find a solution.
Round Trip Delay (RTD)
The pilot timing on the forward link of each sector in the base station is synchronized with GPS system time. The mobile station time reference is the time of occurrence, as measured at the mobile station antenna connector of the earliest arriving usable multipath component being used in the demodulation. The mobile station time reference is used as the transmit time of the reverse traffic and access channels.
FIG. 2 shows one terrestrial transceiver station 201 and a mobile station 202. As shown in FIG. 2, the mobile 202 uses the received time reference from the serving base station 201 as its own time reference. Accounting for its own hardware and software delays, the mobile station transmits its signal such that it is received back at the serving base station 201 delayed by a total of 2.tau., assuming that the forward and reverse links have essentially equal propagation delays. The total delay is measured at the base station by correlating the received signal from the mobile station 202 with the referenced signal at time T.sub.sys. The measured RTD corresponds to twice the distance between the mobile 202 and the base station 201 (after calibration of base station side hardware delays).
Note that knowledge of the PN of the serving base station can also be used (due to sectorization as a rough angle of arrival (AOA) measurement) to help with resolving ambiguity.
Pilot Phase Measurements
The mobile station is continuously searching for active and neighboring pilots. In the process, it measures the PN offset of each pilot it receives. If the time reference is the same on both PN offset and satellite measurements then the bias on these measurements (as measured at the corresponding antenna connector) will be the same. They can then both be regarded as pseudo-ranges.
If the time references are different then we can simply use PN offset differences between each pilot and the reference (earliest arrival) pilot. The pilot PN phase difference is the same as time difference of arrival (TDOA) of the two pilots from the two base stations. FIG. 4 shows two such base stations 401, 402 and a mobile station 405.
Note that on most cellular system's antennas are sectorized and each PN is associated with a sector rather than with a base station. Hence, each measurement can provide, in addition to the TDOA information, some level of angle of arrival information (AOA) that can be used to resolve ambiguity.
Altitude Aiding Measurement
It is always possible to determine with which sector the phone is communicating. This can give an estimate of the phones position to within three to five kilometers. Network planning is usually done based on digital maps of the coverage area. Based on terrain information and knowledge of the sector it is always possible to obtain a good estimate of the user elevation.
3-D Positioning with Three Satellites
FIG. 3 shows three satellites 301, 302, 303, a terrestrial transceiver station 304, and a mobile station 305. As shown in FIG. 3, since the mobile station 305 is receiving CDMA signals from at least one base station 304, the mobile 305 will acquire system time. Its sense of system time is delayed with respect to true system time at the serving base station 304 by the propagation delay .tau. between the mobile station 305 and base station 304. Once the mobile station 305 tries to access the system, or is on the traffic channel, the propagation delay .tau. is estimated by ##EQU1##
This estimate can be used to adjust the mobile system time to correspond to "true" GPS time. Now a mobile clock within the mobile station 305 is synchronized with GPS time; hence only three measurements from three satellites 301, 302, 303 are needed. Note that multipath does not impact the performance of the system because the mobile system time is shifted from GPS time by .tau. regardless of whether the signal took a direct path or a reflected path. Instead of the RTD measurement at the base station 30, the mobile station's measurement of the pilot phase offset can be used to reduce to three the number of satellites required.
3-D Positioning with Two Satellites
In addition to using the RTD to the serving base station for timing, the serving base station can also be used for ranging, as shown in FIG. 5. FIG. 5 shows two satellites 501, 502, a base station 504, and a mobile station 505. The distance to the serving base station 504 is given by R.sub.3 =C.tau. where C is the speed of light. Multipath here will impact positioning accuracy. Note that under certain geometry scenarios, we may get two ambiguous solutions. The ambiguity can be resolved by using either sectorization or forward link information. For example, pilot PN phase difference of a neighboring pilot can be used to resolve the resulting ambiguity. Also, pilot phase measurements may be used instead of, or in addition to, the RTD measurement.
3-D Positioning with One Satellite
In this scenario, the proposed approach requires one additional measurement from the cellular/PCS network. This additional measurement could be either a second RTD measurement or a pilot phase offset on the forward link. FIG. 6 illustrates a satellite 601, two terrestrial transceiver stations 604, and a mobile station 605. To reduce the impact of multipath on the calculated position, the mobile station 605 reports the pilot phase of the earliest arriving path.
When combining different types of measurements, iterative solutions (such as the well-known "Newton-algorithm" based gradient approach) may be used to determine the solution (i.e., the position of the device sought). However, in certain scenarios in which an iterative solution is used, two solutions are possible. Two solutions are possible because of the quadratic nature of the measurements that are used in the iterative equation (i.e., the fact that at least one of the unknowns for which a solution is required are raised to the second power). The possible existence of two solutions creates ambiguity in the solution. That is, it is not clear which of the two solutions represent the location sought. This applies to all the types of positioning systems (except AOA) including the Global Positioning System (GPS).
The existence of ambiguity dependents on the existence of measurement redundancy and on the relative locations of the satellites and terrestrial transceiver stations that provide location information. There is always ambiguity when there is no redundancy in the measurements. However, ambiguity also always exists when there is redundancy, but the geometry is such that the amount of information provided is insufficient, even in light of additional measurements. However, these are rare occurrences.
An iterative method will converge to one of the solutions without any indication of the existence or position of the other solution. The particular solution to which it converges will depend solely on the initial condition used.
In the case of GPS, because of the distance of the satellites, the ambiguous solution is typically very far from the surface of the Earth. It is therefore impossible that the iterative method would converge to the wrong solution if given an initial condition close to the surface of the earth. However, when combining satellite measurements with base station measurements it is very possible that the two ambiguous solutions will be close to each other. The iterative method would thus converge arbitrarily to one of the two solutions without a clear determination as to whether the solution to which it converged was the correct solution, or whether there are two solutions at all.
An exhaustive search can be performed to identify both solutions, if two solutions exist. However, if only one solution exists, it may be necessary to run the Least Mean Square (LMIS) iterative process several times before a determination can be made that only one solution exists.
The algebraic method presented by Bancroft ("An Algebraic Solution of the GPS equations", published by IEEE on Jan. 8, 1984) and by Schipper ("Utilization of Exact Solutions of the Pseudo-range Equations", U.S. Pat. No. 5,914,686, filed Aug. 5, 1997) both require that all measurements have the same time bias. This is a constraining requirement on the types of measurements that can be used with an algebraic method. Accordingly, when measurements from a CDMA communications system base station are being used as one of the sources of information, PN phase measurements are used to determine the pseudo-range to the base station. The use of PN phase measurement requires that the GPS receiver be synchronized with the cellular transceiver not only with respect to clock frequency, but also with respect to clock phase.
As noted above, another measurement that is advantageous to use is the measurement of RTD between the device whose location is being sought and a terrestrial transceiver station, such as a cellular communication base station.
However, since the time bias in the range measurement that results from the measurement of RTD (which is zero) is not the same as the time bias associated with the GPS measurements, the range measurement that is derived from RTD cannot be used in the algebraic solution at all. In order for the algebraic method to be the most useful method for identifying ambiguous solutions, the method should be able to make use of all the measurements that are available.
A more versatile algebraic method and apparatus for performing the method for use with hybrid positioning system equations is therefore described.